package 链表和树.链表;
//Java：重排链表
public class ReorderList{
    public static void main(String[] args) {
        Solution solution = new ReorderList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class ListNode {
//        int val;
//        ListNode next;
//        ListNode() {}
//        ListNode(int val) { this.val = val; }
//        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//    }
class Solution {
    public void reorderList(ListNode head) {
        //1.先找到链表的中间节点
        ListNode slow = new ListNode();
        ListNode fast = new ListNode();
        while (fast!= null&&fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow;
        //2.翻转链表
        ListNode pre = null;
        while(mid != null){
            ListNode nxt = mid.next;
            mid.next = pre;
            pre = mid;
            mid = nxt;
        }
        ListNode head2 = pre;
        //3.循环往复需保存两个head的next
        while (head2.next != null){
            ListNode nxt = head.next;
            ListNode nxt2 = head2.next;
            head.next = head2;
            head2.next = nxt;
            head = nxt;
            head2 = nxt2;

        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}